Design and Implementation of Metabolic Pathway Based on Multi-path Breadth-first Searching Algorithm

To find possible reactions that exist in metabolic networks is essential for metabolic engineering. The K-shortest path (KSP) algorithm is a traditional method that is usually used to identify alternative metabolic pathways. To improve the computation efficiency of conventional KSP method, an efficient KSP-based searching method is proposed in this paper. The basic idea is to introduce the critical edge to reduce the redundant calculation. A web-platform is constructed to design metabolic pathways. The parallel computing technique is introduced to improve the computing efficiency. The proposed method is validated on the KEGG metabolic pathways map, and the results show that the proposed method improve the computation efficiency by 5-9 times, compared with the traditional KSP algorithm.